package pprg.quicksort;

public class QuickSortSequential {

	public int[] values; // array to be sorted

	public int[] getValues() {
		return values;
	}

	public void sorting(int[] values) {
		
		// array must have at least one element
		if (values == null || values.length == 0) {
			return;
		}
		
		this.values = values;
		int count = values.length;
		quicksort(0, count - 1);
	}

	private void quicksort(int left, int right) {
		
		int i = left, j = right;
		
		// pick pivot element from the middle of the list
		int pivotindex = left + (right - left) / 2;
		int pivot = values[pivotindex];

		
		// divide into one part which is smaller than pivot
		// and one which is greater than pivot
		while (i <= j) {
		
			// element is smaller than pivot -> correct -> next element
			while (values[i] < pivot) {
				i++;
			}
			
			// element is greater than pivot -> correct -> next element
			while (values[j] > pivot) {
				j--;
			}

			// value greater than pivot in left array
			// and value smaller than pivot in right -> swap
			if (i <= j) {
				swap(i, j);
				i++;
				j--;
			}
		}

		if (left < j)
			quicksort(left, j);
		if (i < right)
			quicksort(i, right);
	}

	private void swap(int i, int j) {
		int temp = values[i];
		values[i] = values[j];
		values[j] = temp;
	}
}
